package leetcode.templates.sorts;

import leetcode.helper.HelpDebug;

public class MaxMergeSort {

	private int nums[];

	public void sort(int[] nums) {
		this.nums = nums;
		process(0, nums.length - 1);
	}

	public void process(int L, int R) {
		if (L == R) {
			return;
		}
		int M = L + ((R - L) >> 1);
		process(L, M);
		process(M + 1, R);
		merge(L, M, R);
	}

	public void merge(int L, int M, int R) {
		int[] help = new int[R - L + 1];
		int p = 0;
		int p1 = L, p2 = M + 1;
		while (p1 <= M && p2 <= R) {
			help[p++] = nums[p1] <= nums[p2] ? nums[p1++] : nums[p2++];
		}
		while (p1 <= M) {
			help[p++] = nums[p1++];
		}
		while (p2 <= R) {
			help[p++] = nums[p2++];
		}
		for (p = 0; p < help.length; p++) {
			nums[L + p] = help[p];
		}
	}

	public static void main(String[] args) {
		MaxMergeSort mss = new MaxMergeSort();
		int[] array = HelpDebug.str2array3("[5,19,2,7,1,10,4,3]");
		mss.sort(array);
		HelpDebug.print(array);
		// [0,1) [l,r)
//		int l = 4, r = 9;
//		for (int i = 0; i < 10; i++) {
//			int ans = (int) (Math.random() * (r - l + 1)) + l;
//			System.out.println(ans);
//		}
	}

}
